class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size(), ret = 0;
        vector<vector<int>> dp(n, vector<int>(n, 0));
        // dp[i][j] 表示：以 i 位置以及 j 位置的元素为结尾的所有的子序列中，等差数列的个数。i < j 
        unordered_map<long long, vector<int>> hash(n);
        for(int i = 0; i < n; ++i)
        {
            hash[nums[i]].push_back(i);
        }
        for(int j  = 2; j < n; ++j) // 固定倒数第一个数
        {
            for(int i = 1; i < j; ++i) // 先固定倒数第二个数
            {
                long long a = (long long)2 * nums[i] - nums[j]; // 防溢出
                if(hash.count(a))
                {
                    for(auto& k : hash[a])
                    {
                        if(k < i)
                            dp[i][j] += dp[k][i] + 1;
                        else
                            break;
                    }
                }
                ret += dp[i][j];
            }
        }
        return ret;
    }
};